package fun.coding.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class WordBreak {

	public static void main(String[] args) {
		String s = "abc";
		System.out.println(s.substring(0, 0));
		
		boolean[] b = new boolean[5];
		System.out.println(b[0]);
		
		Set<String> dic = new HashSet<String>();
		dic.add("cat");
		dic.add("cats");
		dic.add("and");
		dic.add("sand");
		dic.add("dog");
		
		WordBreak wb = new WordBreak();
		String test1 = "catsanddog";
		String test2 = "catsandogg"; 
		
		System.out.println(wb.wordBreak(test1, dic));
		System.out.println(wb.wordBreak(test2, dic));

	}

	public boolean wordBreak(String s, Set<String> dict) {
		Map<String, Boolean> m = new HashMap<String, Boolean>();
		return wordBreakHelper(s, dict, m);

	}

	// What about the time complexity? still exponential. 
	public boolean wordBreakHelper(String s, Set<String> dict, Map<String, Boolean> lookup) {
		if (dict.contains(s)) {
			return true;
		}

		if (lookup.containsKey(s)) {
			return lookup.get(s);
		}

		for (int i = 0; i < s.length(); ++i) {
			if (dict.contains(s.substring(0, i))) {
				String sub = s.substring(i, s.length());

				if (!wordBreakHelper(sub, dict, lookup)) {
					lookup.put(sub, false);
				} else {
					lookup.put(sub, true);
					return true;
				}
			} 
		}

		lookup.put(s, false);
		return false;
	}

	// We actually don't need a hashtable to store all the combinations, 
	// e.g., abcdef, we only care if abcdef can be break or not, don' care about bcde can be broken or not
	// Thus don't need a map, an array is enough
	public boolean wordBreakDp(String s, Set<String> dict) {
		if (s == null || s.isEmpty()) return false;
		
		boolean[] lookup = new boolean[s.length() + 1];
		lookup[0] = true;
		
		for (int i = 1; i <= s.length(); ++i) {
			for (int j = i; j >= 1; j--) {
				if (dict.contains(s.substring(j-1, i)) && lookup[j - 1]) {
					if (dict.contains(s.substring(j-1, s.length()))) {
						return true;
					}
					lookup[i] = true;
					break;
				}
			}
		}
		
		return lookup[s.length()];
	}
	
	// This is almost like brute force, exponential 
	public boolean wordBreakTimeLimitExceed(String s, Set<String> dict) {
		if (dict.contains(s)) {
			return true;
		}

		for (int i = 1; i < s.length(); ++i) {
			if (dict.contains(s.substring(0, i)) && wordBreakTimeLimitExceed(s.substring(i, s.length()), dict)) {
				return true;
			} 
		}

		return false;
	}

}
